/**
 * \file ArbreCousu.inl
 * \brief Le code des op�rateurs d'un arbre couture.
 * \author Abder
 * \version 0.1
 * \date septembre 2011
 *
 * Impl�mentation par cha�nage
 *
 */


/**
 * \fn ArbreCousu<T>::ArbreCousu() 
 */
template <typename T>
ArbreCousu<T>::ArbreCousu()
{
	racine = 0;
	cpt = 0;
}

/**
 * \fn ArbreCousu<T>::ArbreCousu(const ArbreCousu& source) throw(std::bad_alloc) 
 *
 * \param[in] source L'arbre source dans la copie
 */
template <typename T>
ArbreCousu<T>::ArbreCousu(const ArbreCousu& source) throw(std::bad_alloc) 
{
	_auxCopier(source.racine,racine);
	cpt = source.cpt;
}

/**
 * \fn const ArbreCousu<T>& ArbreCousu<T>::operator = (const ArbreCousu & source) throw(std::bad_alloc) 
 *
 * \param[in] source L'arbre source dans l'assignation
 */
template <typename T>
const ArbreCousu<T>& ArbreCousu<T>::operator = (const ArbreCousu & a) throw(std::bad_alloc) 
{ 
	_auxDetruire(racine); 
	_auxCopier(a.racine,racine);
	cpt = a.cpt;
	return (*this);
}


/**
 * \fn ArbreCousu<T>::~ArbreCousu() 
 */
template <typename T>
ArbreCousu<T>::~ArbreCousu() 
{
	_auxDetruire(racine);
}

/**
 * \fn typename ArbreCousu<E>:: Noeud* ArbreCousu<E>:: _auxAppartient(Noeud* & arbre, const E &data) const
 *
 * \param[in] arbre Le sous-arbre dans lequel on effectue la recherche
 * \param[in] data L'�l�ment recherch� dans le sous-arbre
 * \return L'adresse du noeud contenant data, NULL si data ne fait pas partie de l'arbre
 */
template <typename E>
typename ArbreCousu<E>::Noeud * ArbreCousu<E>:: _auxAppartient(Noeud* arbre, const E &data) const
{	
	if (arbre == 0)
	{
		return 0;
	}
	if ( arbre->data == data  )
	{
		return arbre;
	}

	if ( arbre->data > data )
	{
		return _auxAppartient(arbre->gauche, data);
	}else
	{
		return _auxAppartient(arbre->droite, data);
	}

}


/**
 * \fn typename ArbreCousu<E>:: Noeud* ArbreCousu<E>:: _parent(Noeud* arb, Noeud* sArb) const throw(std::logic_error)
 *
 * \param[in] arb L'adresse du sous-arbre dans lequel on effectue la recherche du parent
 * \param[in] sArb L'adresse du noeud dont on cherche son parent
 * 
 * \return L'adresse du noeud parent
 */
template <typename E>
typename ArbreCousu<E>:: Noeud* ArbreCousu<E>:: _parent(Noeud* arb, Noeud* sArb) const throw(std::logic_error)
{	
	if (arb == 0)
		throw std::logic_error("Parent: l'arbre est vide!\n");

	if (sArb == 0)
		throw std::logic_error("Parent: l'element dont on cherche son parent n'existe pas!\n");
	
	if (sArb == arb)
		throw std::logic_error("Parent: Le parent de la racine d'existe pas!\n");

	if ( sArb->data < arb-> data ) 
	{
		if (arb->gauche == sArb)
		{
			return arb;
		}else
		{
			return _parent(arb->gauche, sArb);
		}
	}else
	{
		if (arb->droite == sArb)
		{
			return arb;
		}else
		{
			return _parent(arb->droite, sArb);
		}
	}
}


/**
 * \fn const E& ArbreCousu<E>::_max(Noeud*racine)const throw (std::logic_error)
 * 
 * \return Le maximum dans le sous-arbre
 */
template<typename E>
const E& ArbreCousu<E>::_max(Noeud*racine)const throw (std::logic_error)
{	
	if (racine==0)
		throw std::logic_error("_max: l'arbre (sous-arbre) est vide!\n");

	if (racine->droite == 0)
	{
		return racine->data;
	}

	return _max(racine->droite);
}


/**
 * \fn E ArbreCousu<E>::_min()const throw (logic_error)
 * 
 * \return Le minimum dans l'arbre
 */
template<typename E>
const E& ArbreCousu<E>::_min(Noeud*racine)const throw (std::logic_error)
{	
	if (racine==0)
		throw std::logic_error("Max: l'arbre (sous-arbre) est vide!\n");

	if (racine->gauche == 0)
	{
		return racine->data;
	}

	return _min(racine->gauche);
}

/**
 * \fn E ArbreCousu<E>:: _successeur(Noeud* arb, const E& info) const throw (std::logic_error)
 *
 * \param[in] arb Le sous-arbre dans lequel on cherche le successeur
 * \param[in] info La donn�e dont on cherche son successeur
 * 
 * \return E- Le successeur de info
 */
template <typename E>
E ArbreCousu<E>:: _successeur(Noeud* arb, const E& info) const throw (std::logic_error)
{	
	if (cpt == 0)
		throw std::logic_error("Successeur: l'arbre est vide!\n");

	Noeud* sArb = _auxAppartient(racine, info);

	if (sArb == 0)
		throw std::logic_error("Successeur: l'element dont on cherche son successeur n'existe pas!\n");

	if ( info == _max(arb))
		throw std::logic_error("Successeur: l'element est le max dans l'arbre, il n'a pas de successeur!\n");

	if (sArb->droite != 0)
	{
		return _min(sArb->droite);
	}
	else
	{
		Noeud * pere = _parent(arb, sArb);
		while (pere->data < sArb->data )
		{
			pere = _parent(arb,pere);
		}

	    return pere->data;
	}
}

/**
 * \fn E ArbreCousu<E>:: _predecesseur(Noeud* arb, const E& info) const throw (std::logic_error)
 *
 * \param[in] arb Le sous-arbre dans lequel on cherche le pr�decesseur
 * \param[in] info La donn�e dont on cherche son pr�decesseur
 * 
 * \return E- Le pr�decesseur de info
 */
template <typename E>
E ArbreCousu<E>:: _predecesseur(Noeud* arb, const E& info) const throw (std::logic_error)
{
   if (cpt == 0)
		throw std::logic_error("Predecesseur: l'arbre est vide!\n");

	Noeud* sArb = _auxAppartient(racine, info);

	if (sArb == 0)
		throw std::logic_error("Predecesseur: l'element dont on cherche son pr�decesseur n'existe pas!\n");

	if ( info == _min(arb))
		throw std::logic_error("Predecesseur: l'element est le min dans l'arbre, il n'a pas de pr�decesseur!\n");

   if (sArb->gauche != 0)
	{
		return _max(sArb->gauche);
	}
	else
	{
		Noeud * pere = _parent(arb, sArb);
		while (pere->data > sArb->data )
		{
			pere = _parent(arb,pere);
		}

	    return pere->data;
	}
}


/**
 * \fn void  ArbreCousu<T>::_auxDetruire(Noeud *&t)
 *
 * \param[in] t Le sous-arbre � d�truire
 * 
 */
template <typename T>
void  ArbreCousu<T>::_auxDetruire(Noeud *& t)
{
	if (t != 0)
	{
		if (t->filGauche == true) t->gauche = 0;
		_auxDetruire(t->gauche);
		if (t->filDroit == true) t->droite = 0;
		_auxDetruire(t->droite);
		delete t;
		t = 0;
	}
}

/**
 * \fn void  ArbreCousu<T>::_auxCopier( Noeud * source, Noeud * & destination) throw(std::bad_alloc)
 *
 * \param[in] source Le sous-arbre � copier
 * \param[out] destination La copie
 */
template <typename T>
void  ArbreCousu<T>::_auxCopier( Noeud * source, Noeud * & destination) throw(std::bad_alloc)
{
	if (source!=0)
	{
		destination = new Noeud(source->data);
		//destination->hauteur = source->hauteur;
		_auxCopier(source->gauche, destination->gauche);
		_auxCopier(source->droite, destination->droite);
	}
	else
		destination=0;
}

/**
 * \fn void ArbreCousu<E>::inserer(const E &data) throw(std::bad_alloc)
 *
 * \param[in] data La donn�e � ins�rer dans l'arbre
 */
template<typename E>
void ArbreCousu<E>::inserer(const E &data) throw(std::bad_alloc)
{
	_auxInserer(racine, data);
}

/**
 * \fn void ArbreCousu<E>::_auxInserer(Noeud *&arbre, const E &data)
 *
 * \param[in] arbre Le sous-arbre dans lequel on ins�re
 * \param[in] data La donn�e � ins�rer dans l'arbre
 * 
 */
template<typename E>
void ArbreCousu<E>::_auxInserer(Noeud *&arbre, const E &data)
{
	if (arbre == 0)
	{
		arbre = new Noeud(data);
		cpt++;
	}
	else if(arbre->data > data )
		_auxInserer(arbre->gauche, data);
	else
		_auxInserer(arbre->droite, data);
}


/**
 * \fn void ArbreCousu<T>:: couture() const
 */
template <typename T>
void ArbreCousu<T>:: couture() const
{ 
	_laCouture(racine);
}

/**
 * \fn typename ArbreCousu<E>:: Noeud * ArbreCousu<E>:: _laCouture(Noeud * sArb) const
 * On trouve tous les noeuds d'un arbre avec la fonction parcoursSymetrique(). 
 * Pour tous les noeuds, on v�rifie si le fils de gauche est null. S'il est null
 * on v�rifie si le noeud en traitement a un pr�d�cesseur avec la fonction
 * predecesseur(). Si le noeud en traitement a un pr�d�cesseur, on fait pointer son
 * fils de gauche sur ce dernier. On fait la m�me chose pour le fils de droit mais
 * cette fois on fait le traitement pour son successeur avec la fonction successeur().
 *
 * \param[in] sArb C'est la racine de l'arbre au premier appel
 * \return La racine de l'arbre mis � jour
 */
template<typename E>
typename ArbreCousu<E>:: Noeud * ArbreCousu<E>:: _laCouture(Noeud * sArb) const
{ 
    E pred;
	E succ;
	
	if(sArb !=0)
	{	
		sArb->gauche = _laCouture(sArb->gauche);
		sArb->droite=  _laCouture(sArb->droite);

		if (sArb->gauche==0 && sArb->filGauche == false && sArb->data!=_min(racine))
		{
			pred=_predecesseur(racine,sArb->data);
			sArb->gauche=_auxAppartient(racine, pred);
			sArb->filGauche=true;
		}

		if (sArb->droite==0 && sArb->filDroit == false && sArb->data!=_max(racine))
		{
			succ=_successeur(racine,sArb->data);
			sArb->droite=_auxAppartient(racine, succ);
			sArb->filDroit=true;
		}
	}

	return  sArb;
}

/**
 * \fn void ArbreCousu<T>::afficherCr() const
 *
 *  Affiche le contenu de l�arbre dans l�ordre de tri croissant.
 */
template <typename T>
void ArbreCousu<T>::afficherCr() const
{ 
	_afficheArbCr(racine);
}

/**
 * \fn void ArbreCousu<E>::_afficheArbCr (Noeud * racine) const
 *
 *  Fonction auxiliaire pour afficher l'arbre dans l�ordre de tri croissant.
 *
 * \param[in] racine la racine de l'arbre cousu
 */
template<typename E>
void ArbreCousu<E>::_afficheArbCr (Noeud * racine) const
{
	Noeud * temp;
  
	if (racine ==0) return;
	temp= racine;
	do
	{
		while (temp->gauche !=0 && temp->filGauche==false) temp = temp->gauche;
		std::cout << temp->data;
		std::cout << std::endl;

		if (temp->droite !=0 && temp->filDroit ==false) 
		{
			temp = temp->droite;
			while (temp->gauche !=0 && temp->filGauche==false) temp = temp->gauche;
			std::cout << temp->data;
			std::cout << std::endl;
		}
		
		if (temp->droite !=0 && temp->filDroit ==true) 
			{
				temp=temp->droite; 
				if (temp!=0) {std::cout << temp->data;
				std::cout << std::endl;}
				
				while (temp!=NULL && temp->filDroit ==true)
				{
					temp=temp->droite; 
					if (temp!=0) {std::cout << temp->data;
					std::cout << std::endl;}
				}
				
			}
		if (temp!=0) temp= temp->droite;
	} while(temp!=0);
}


/**
 * \fn void ArbreCousu<T>::afficherDe() const
 *
 *  Affiche le contenu de l�arbre dans l�ordre de tri d�croissant.
 */
template <typename T>
void ArbreCousu<T>::afficherDe() const
{ 
	_afficheArbDe (racine);
}


/**
 * \fn void ArbreCousu<E>::_afficheArbDe (Noeud * racine) const
 *
 *  Fonction auxiliaire pour afficher l'arbre dans l�ordre de tri d�croissant.
 *
 * \param[in] racine la racine de l'arbre cousu
 */
template<typename E>
void ArbreCousu<E>::_afficheArbDe (Noeud * racine) const
{
  // à faire
	Noeud * temp;
	  
		if (racine ==0) return;
		temp= racine;
		do
		{
			while (temp->droite !=0 && temp->filDroit==false) temp = temp->droite;
			std::cout << temp->data;
			std::cout << std::endl;

			if (temp->gauche !=0 && temp->filGauche ==false) 
			{
				temp = temp->gauche;
				while (temp->droite !=0 && temp->filDroit==false) temp = temp->droite;
				std::cout << temp->data;
				std::cout << std::endl;
			}
			
			if (temp->gauche !=0 && temp->filGauche ==true) 
				{
					temp=temp->gauche; 
					if (temp!=0) {std::cout << temp->data;
					std::cout << std::endl;}
					
					while (temp!=NULL && temp->filGauche ==true)
					{
						temp=temp->gauche; 
						if (temp!=0) {std::cout << temp->data;
						std::cout << std::endl;}
					}
					
				}
			if (temp!=0) temp= temp->gauche;
		} while(temp!=0);
}
